#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return nullptr;

        int rootValue = preorder[0];
        TreeNode* root = new TreeNode(rootValue);
        if (preorder.size() == 1) return root;

        int delimterIndex;
        for (delimterIndex = 0; delimterIndex < inorder.size(); delimterIndex++)
        {
            if (inorder[delimterIndex] == rootValue) break;
        }
        //[begin,delimterIndex),[delimterIndex+1,end)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimterIndex);
        vector<int> rightInorder(inorder.begin() + delimterIndex + 1, inorder.end());

        vector<int> preorder1(preorder.begin() + 1, preorder.end());

        vector<int> leftPreorder(preorder1.begin(), preorder1.begin() + delimterIndex);
        vector<int> rightPreorder(preorder1.begin() + delimterIndex, preorder1.end());

        root->left = buildTree(leftPreorder, leftInorder);
        root->right = buildTree(rightPreorder, rightInorder);
        return root;
    }
};